package com.heima.leetcode.practice;

/**
 * leetcode 50. Pow(x, n) 快速幂
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/13 22:00
 */
public class E50 {
    /**
     * 快速幂
     * @param x x
     * @param n n
     * @return 结果
     */
    public double myPow(double x, int n) {
        // if (n < 0) n = -n; // 遇到负数的最小值就寄了，取反越界
        long p = n;
        if (n < 0) p = -p;
        double result = myPowPositive(x, p);
        return n < 0 ? 1 / result : result;
    }

    /**
     * 快速幂，n为正数
     * @param x x
     * @param n n
     * @return 结果
     */
    private double myPowPositive(double x, long n) {
        if (n == 0) return 1;
        double y = myPowPositive(x, n >> 1); // 这里不需要记忆法或者动态规划优化，因为这条递归会一直到头
        if ((n & 1) == 1){
            return x * y * y;
        }else {
            return y * y;
        }
    }
}
